package com.wenhai.leetcode.array;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 *
 * @author wenhai
 * @date 2021/2/23
 */
public class 剑指Offer_51数组中的逆序对 {
    public int reversePairs2(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    res++;
                }
            }
        }
        return res;
    }


    public int reversePairs(int[] nums) {
        int[] tempArr = Arrays.copyOf(nums, nums.length);
        return sort(nums, 0, nums.length - 1, tempArr);
    }

    private int sort(int[] nums, int l, int r, int[] tempArr) {
        int res = 0;
        if (l >= r) {
            return res;
        }
        int mid = l + ((r - l) >>> 1);
        res += sort(nums, l, mid, tempArr);
        res += sort(nums, mid + 1, r, tempArr);
        if (nums[mid] > nums[mid + 1]) {
            res += merge(nums, l, mid, r, tempArr);
        }
        return res;
    }

    private int merge(int[] nums, int l, int mid, int r, int[] tempArr) {
        int res = 0;
        System.arraycopy(nums, l, tempArr, l, r - l + 1);
        int j = mid + 1;
        int k = l;
        for (int i = l; i <= r; i++) {
            if (k > mid) {
                nums[i] = tempArr[j++];
            } else if (j > r) {
                nums[i] = tempArr[k++];
            } else if (tempArr[k] < tempArr[j]) {
                nums[i] = tempArr[k++];
            }else {
                res += mid - k + 1;
                nums[i] = tempArr[j++];

            }
        }
        return res;
    }

    public static void main(String[] args) {
        new 剑指Offer_51数组中的逆序对().reversePairs(new int[]{7, 5, 6, 4});

    }
}
